package drds.server.buffer;

import java.nio.ByteBuffer;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import sun.nio.ch.DirectBuffer;

/**
 * 一堆page的集合(一块连续内存)<br/>
 * 由memoryMap和depthMap定义成一种平衡二叉树的管理结构
 * 
 * @author 曹正辉<330937205@qq.com>
 * 
 */
public class Block implements Comparable<Object> {
	private static final Logger LOGGER = LoggerFactory.getLogger(Block.class);
	private final byte[] memoryMap;
	private final byte[] depthMap;
	private final ByteBuffer byteBuffer;

	// in bytes
	private final int pageSize;
	// in bytes
	private final int blockSize;
	private final int pageNumInBlock;
	/**
	 * log2(this.pageNumInBlock) + 1;
	 */
	private final int maxDepth;
	private final byte unusable;
	private final int log2PageSize;
	final long byteBufferAddress;
	/**
	 * 空余字节
	 */
	private int freeBytes;

	Block prev;
	Block next;
	BlockList parent;

	public Block(int blockSize, int pageSize) {

		this.blockSize = blockSize;
		this.pageSize = pageSize;
		this.pageNumInBlock = blockSize / pageSize;
		//

		this.maxDepth = log2(this.pageNumInBlock) + 1;
		this.unusable = (byte) this.maxDepth;
		//
		this.byteBuffer = ByteBuffer.allocateDirect(blockSize);
		this.byteBufferAddress = ((DirectBuffer) byteBuffer).address();
		this.freeBytes = blockSize;

		this.depthMap = new byte[(1 << this.maxDepth)];
		this.memoryMap = new byte[this.depthMap.length];
		// 分配完成后，
		// memoryMap->[0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3…]
		// depthMap ->[0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3…]

		this.log2PageSize = log2(pageSize);

		// 第一个节点作为无用的节点:index=0无用
		int memoryMapIndex = 1;
		for (int i = 0; i < maxDepth; ++i) {
			// move down the tree one level at a time
			int depth = 1 << i;
			for (int j = 0; j < depth; ++j) {
				// in each level traverse left to right and set value to the
				// depth of subtree
				memoryMap[memoryMapIndex] = (byte) i;// Depth
				depthMap[memoryMapIndex] = (byte) i;// Depth
				memoryMapIndex++;// 为每个数组元素绑定的Index
			}
		}
	}

	public boolean isIn(ByteBuffer byteBuffer) {
		long address = ((DirectBuffer) byteBuffer).address();
		return (address >= byteBufferAddress) && //
				(address < byteBufferAddress + blockSize);
	}

	/**
	 * 已经使用率
	 */
	public int usage() {
		final int freeBytes = this.freeBytes;
		if (freeBytes == 0) {
			return 100;
		}

		int freePercentage = (int) (freeBytes * 100L / blockSize);
		if (freePercentage == 0) {
			return 99;
		}
		return 100 - freePercentage;
	}

	public synchronized ByteBuffer allocateByteBuffer(int capacity) {
		if (capacity > blockSize) {
			LOGGER.error("try to acquire a buffer with larger size than chunkSize!");
			return null;
		}
		int d = this.maxDepth - 2 - (log2(capacity) - this.log2PageSize);
		if (d > this.maxDepth - 1) {
			d = maxDepth - 1;
		}
		int id = allocateNode(d);
		if (id < 0) {
			return null;
		}
		freeBytes -= runLength(id);

		int start = calculateStart(id);
		int end = start + runLength(id);

		byteBuffer.limit(end);
		byteBuffer.position(start);
		return byteBuffer.slice();
	}

	private int calculateStart(int id) {
		int count = 0;
		for (int i = 1; i < depthMap.length; i++) {
			if (depthMap[i] < depthMap[id]) {
				continue;
			} else if (depthMap[i] == depthMap[id]) {
				if (i == id) {
					break;
				} else {
					count += runLength(i);
				}
			} else {
				break;
			}
		}
		return count;
	}

	private int runLength(int id) {
		// represents the size in #bytes supported by node 'id' in the tree
		return 1 << log2(blockSize) - depthMap[id];
	}

	/**
	 * allocateNode(int d)传入的参数为depth, 通过depth来搜索对应层级第一个可用的node id
	 */
	private int allocateNode(int depth) {
		int id = 1;
		int initial = -(1 << depth); // has last d bits = 0 and rest all = 1
		// 第一层
		byte val = memoryMap[id];
		if (val > depth) { // unusable
			return -1;
		}

		while (val < depth || (id & initial) == 0) { // id & initial == 1 << d
														// for
			// all ids at depth d, for <
			// d it is 0
			id <<= 1;
			val = memoryMap[id];
			// 切换到右节点
			if (val > depth) {
				id ^= 1;
				val = memoryMap[id];
			}
		}
		byte value = memoryMap[id];
		assert value == depth && (id & initial) == 1 << depth : String.format("val = %d, id & initial = %d, d = %d", value, id & initial, depth);
		memoryMap[id] = unusable; // mark as unusable
		updateParentsAlloc(id);
		return id;
	}

	private void updateParentsAlloc(int id) {
		while (id > 1) {
			int parentId = id >>> 1;
			byte val1 = memoryMap[id];
			byte val2 = memoryMap[id ^ 1];
			// 得到左节点和右节点较小的值赋给父节点，即两个节点只要有一个可分配，则父节点的值设为可分配的这个节点的值
			byte val = val1 < val2 ? val1 : val2;
			memoryMap[parentId] = val;
			id = parentId;
		}
	}

	public synchronized void freeByteBuffer(ByteBuffer byteBuffer) {
		long address = ((DirectBuffer) byteBuffer).address();
		int $address = (int) (address - byteBufferAddress);
		int length = byteBuffer.capacity();

		int depth = maxDepth - 1 - log2(length / pageSize);
		int count = 0;
		int i;
		for (i = 0; i < depthMap.length; i++) {
			if (depthMap[i] == depth) {
				if (count == $address) {
					break;
				}
				count += length;
			}
			if (depthMap[i] > depth) {
				break;
			}
		}
		free(i);
	}

	private void free(int handle) {
		if (memoryMap[handle] != depthMap[handle]) {
			freeBytes += runLength(handle);
			memoryMap[handle] = depthMap[handle];
			updateParentsFree(handle);
		}
	}

	private void updateParentsFree(int id) {
		int logChild = depthMap[id] + 1;
		while (id > 1) {
			int parentId = id >>> 1;
			byte val1 = memoryMap[id];
			byte val2 = memoryMap[id ^ 1];
			logChild -= 1; // in first iteration equals log, subsequently reduce
			// 1 from logChild as we traverse up

			if (val1 == logChild && val2 == logChild) {
				memoryMap[parentId] = (byte) (logChild - 1);
			} else {
				byte val = val1 < val2 ? val1 : val2;
				memoryMap[parentId] = val;
			}

			id = parentId;
		}
	}

	/**
	 * log2(val)=Integer.SIZE - 1 - Integer.numberOfLeadingZeros(val)
	 */
	private static int log2(int blockSize) {
		if (blockSize <= 0) {
			LOGGER.error("invalid parameter!");
			throw new IllegalArgumentException();
		}
		/**
		 * floor(log2(x)) = 31 - numberOfLeadingZeros(x)
		 */
		return Integer.SIZE - 1 - Integer.numberOfLeadingZeros(blockSize);
	}

	@Override
	public int compareTo(Object o) {
		return -1;
	}
}
